package leetcode.code2101;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int maximumDetonation(int[][] bombs) {
		int len = bombs.length;
		List<Integer>[] nexts = new ArrayList[len];
		for (int i = 0; i < len; i++) {
			int[] b1 = bombs[i];
			int x1 = b1[0], y1 = b1[1], r1 = b1[2];
			nexts[i] = new ArrayList<>();
			List<Integer> list = nexts[i];
			for (int j = 0; j < len; j++) {
				if (i != j) {
					int[] b2 = bombs[j];
					int x2 = b2[0], y2 = b2[1], r2 = b2[2];
					long dist1 = Math.abs(x1 - x2);
					long dist2 = Math.abs(y1 - y2);
					if (dist1 * dist1 + dist2 * dist2 <= (long)r1 * r1) {
						list.add(j);
					}
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < len; i++) {
			boolean[] bbb = new boolean[len];
			bbb[i] = true;
			Queue<Integer> queue = new LinkedList<>();
			queue.add(i);
			int cur = 0;
			while (!queue.isEmpty()) {
				int b = queue.poll();
				List<Integer> next = nexts[b];
				cur++;
				for (int n : next) {
					if (!bbb[n]) {
						bbb[n] = true;
						queue.add(n);
					}
				}
			}
			ans = Math.max(ans, cur);
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(1, this.maximumDetonation(H.str2array1("[[1,1,100000],[100000,100000,1]]")));
		H.compare(2, this.maximumDetonation(H.str2array1("[[2,1,3],[6,1,4]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		int r = 100000;
		System.out.println(r * r);
		System.out.println((long)r * r);
	}

}
